A technology of key exchange is disclosed in NPL 1. Specifically, two key exchange devices, each of which knows a public key of the other, exchange encrypted data into which random tapes input to the respective key exchange devices are encrypted with a long-term secret key of their own. Each key exchange device generates a session key based on the encrypted data received from the other party of exchange, the public key of the other party of exchange, and the long-term secret key of its own. As a result, the session keys that are generated by the two key exchange devices become identical. Unless the random tapes used for generation of the session keys and the long-term secret keys are stolen by an attacker, the session keys are concealed from the attacker.